package com.meterhuang;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * [middle]
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 *  
 * @author meterhuang
 * @since 2021/04/01
 */
@Slf4j
public class SubSet {

	private static List<List<Integer>> ans = new ArrayList<>();
	private static List<Integer> t = new ArrayList<>();

    public static void main(String[] args) {
		int[] nums = {2, 1, 2, 1, 3};
		binaryFind(nums);
        log.info("二进制迭代法: {}", ans);
        ans.clear();
        // 位运算能存消耗略大，但速度更快，前者速度较慢但内存消耗略小
        binaryFindV2(nums);
        log.info("二进制迭代法优化: {}", ans);
		// 回溯法：递归
		ans.clear();
		t.clear();
		subsets(nums);
		log.info("回溯法: {}", ans);
    }

	/**
	 * 二进制法穷举子元素集合
	 * [2,1,2,1,3]，子集总数共2^5个
	 * 0表示不在集合中，1表示在集合中
	 * eg: 00001 => [3]
	 *
	 * @param nums
	 */
	private static void binaryFind(int[] nums) {
    	for (int mask = 0; mask < (1 << nums.length); ++mask) {
    		t.clear();
    		for (int pos = 0; pos < nums.length; ++pos) {
    			// 使用异或定位该元素在子集中是否存在，只要>0即表示匹配
    			if ((mask & (1 << pos)) > 0) {
    				t.add(nums[pos]);
				}
			}
			List<Integer> collect = t.stream().sorted().collect(Collectors.toList());
			ArrayList<Integer> sub = new ArrayList<>(collect);
			if (!ans.contains(sub)) {
				ans.add(sub);
			}
		}
	}

	/**
	 * 二进制法穷举子元素集合遍历过程中去重
	 * 去重规则：对于已经排好序的数组，如果遍历至位置i,和i-1位置上的元素一样，并且当前子元素集合中不包含i-1，则跳过当前子集
	 * 数学依据：如果元素x,y均属于某一个集合且x和y相等，则包含x的子集必然和包含y的子集一致
	 *
	 * @param nums
	 */
	private static void binaryFindV2(int[] nums) {
		Arrays.sort(nums);
		for (int mask = 0; mask < (1 << nums.length); ++mask) {
			t.clear();
			boolean flag = true;
			for (int pos = 0; pos < nums.length; ++pos) {
				// 使用异或定位该元素在子集中是否存在，只要>0即表示匹配
				if ((mask & (1 << pos)) > 0) {
					if (pos > 0 && ((mask & (1 << (pos - 1))) == 0) && nums[pos] == nums[pos - 1]) {
						flag = false;
						break;
					}
					t.add(nums[pos]);
				}
			}
			if (flag) {
				ans.add(new ArrayList<>(t));
			}
		}
	}

	/**
	 * 回溯法
	 *
	 * 对于一个有序的数组，如果当前元素在组件子集时，前一个元素若与之相等，并且前一个元素不包含在当前的子集中，则跳出当前组建过程
	 * 数学依据：如果元素x,y均属于某一个集合且x和y相等，则包含x的子集必然和包含y的子集一致
	 * @param nums
	 */
	public static void subsets(int[] nums) {
		Arrays.sort(nums);
		//dfs(false, 0, nums);
		dfsReverse(true, 0, nums);
		//dfs(0, nums);
	}

	/**
	 * 递归
	 *
	 * @param choosePre 是否选中上一个元素
	 * @param cur 游标
	 * @param nums 数组
	 */
	public static void dfs(boolean choosePre, int cur, int[] nums) {
		if (cur == nums.length) {
			ans.add(new ArrayList<>(t));
			return;
		}
		// 不包含当前元素
		dfs(false,cur + 1, nums);
		if (!choosePre && cur > 0 && nums[cur] == nums[cur -1]) {
			return;
		}
		// 包含当前元素
		t.add(nums[cur]);
		dfs(true,cur + 1, nums);
		t.remove(t.size() - 1);
	}

	/**
	 * 递归:dfs的另一个版本
	 *
	 * @param choosePre 是否选中上一个元素
	 * @param cur 游标
	 * @param nums 数组
	 */
	public static void dfsReverse(boolean choosePre, int cur, int[] nums) {
		if (cur == nums.length) {
			ans.add(new ArrayList<>(t));
			return;
		}
		// 包含当前元素
		t.add(nums[cur]);
		dfs(true,cur + 1, nums);
		if (!choosePre && cur > 0 && nums[cur] == nums[cur -1]) {
			return;
		}
		// 不包含当前元素
		t.remove(t.size() - 1);
		dfs(false,cur + 1, nums);
	}

	/**
	 * 不去重
	 * @param cur 序号
	 * @param nums 序列数组
	 */
	public static void dfs(int cur, int[] nums) {
		if (cur == nums.length) {
			ans.add(new ArrayList<>(t));
			return;
		}
		// 考虑选择当前位置
		t.add(nums[cur]);
		dfs(cur + 1, nums);
		// 考虑不选择当前位置
		t.remove(t.size() - 1);
		dfs(cur + 1, nums);
	}
}
